#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int twofind(vector<int>& arr, int x) {
        int left = 0, right = arr.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] == x) return mid;
            else if (arr[mid] < x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
    int LIS(vector<int>& a) {
        int n = a.size();
        if (n == 0) return 0;
        vector<int> ret;
        ret.push_back(a[0]);
        for (int i = 1; i < n; i++) {
            int x = twofind(ret, a[i]);
            if (x == 0 && ret[x] >= a[i]) ret[x] = a[i];
            else if (x + 1 == ret.size()) ret.push_back(a[i]);
            else ret[x + 1] = a[i];
        }
        return ret.size();
    }
};